In the development of new electronic products, it is necessary to test and debug both the hardware and software of these products. These testing and debugging operations are key factors to bringing new products to market.
To perform these testing and debugging operations on computers or digital circuits, engineers frequently use an instrument called a "logic analyzer." In its most common use, a logic analyzer periodically samples (or captures) and stores the states of several digital signals at the same time.
In use, a logic analyzer records or "traces" the behavior of the computer or digital circuit over a period of time. To do this, the logic analyzer is periodically activated to sample the states of a predetermined number of digital signals.
The record of the computer's or digital circuit's behavior over a prescribed period of time is referred to as a "logic trace." Such an array may also be referred to as a "logic trace array" or simply a "trace array". Since this array only contains "0s" and "1s," a trace array also may be referred to as a "binary array." Although there may be various ways of organizing the trace array, a preferred method is a two dimensional array such as the representative prior art trace array shown in FIG. 1.
In FIG. 1, the representative trace array is shown generally at 100. Each entry in the array is either "1" or "0," and represents the state of one digital signal from a computer or other digital circuit at one point in time. The trace array at 100 has representative rows 102, 104, 106, 108, 110 and 112, and representative columns 114, 116, 118, 120, 122, and 124.
In the trace array at 100, all of the entries for one signal are in a single column in the order in which sampling takes place. This is so each column traces the behavior of one particular digital signal over time. Each row contains the state of all the signals at one particular point in time. As such, a row is a "sample" of all the signals at a particular point in time.
For many years, logic analyzers could collect only small arrays such as that shown in FIG. 1. That is, logic analyzers could only store arrays having up to 4,096 to 8,192 samples (rows) and 48 to 64 signals (columns). Arrays of this size could be printed out on paper and then analyzed by hand to understand the circuit behavior recorded in the trace array. This permitted desired signal patterns to be viewed and evaluated with little trouble for their frequency and affect on the computer or digital circuit being tested.
It has been found that the usefulness of logic trace arrays of the size shown in FIG. 1 is limited for testing and debugging purposes because such traces cover only a very small time window of sampled data. Therefore, in many cases, very complex circuit problems could not be solved using these small size trace arrays. Hence, it is desirable to have a much larger time window of captured data for analyzing more complex circuit behavior and a method to analyze larger trace arrays that provide larger time windows.
Today, we have logic analyzers that generate much larger trace arrays than that shown in FIG. 1. These new powerful tools provide much larger time windows for data acquisition for sampling the behavior of computers or digital circuits. For example, logic analyzers now have been built to collect trace arrays as large as 524,288 samples of 192 signals, or 2,097,152 samples of 64 signals. These trace arrays, however, are too large to print out on paper and analyzer by hand. There is a need for a practical and an efficient way to analyze these larger trace arrays that heretofore has not been available. A consideration may be to look to known pattern searching methods such as those used for searching text files.
A known method for searching for particular patterns in text files is to define the desired pattern as a regular expression. From the regular expression, a finite automaton is generated. The finite automaton then is used to search the text file for the desired pattern.
Regular expressions are a useful way to describe the kinds of patterns engineers search for when analyzing trace arrays. Furthermore, using finite automata generated from regular expressions is an efficient technique for pattern searching.
A regular expression is compiled into a recognizer that is used for pattern searching by constructing a transition diagram that is called a finite automaton. A recognizer is a program that takes an input string and answers "yes" if the string matches a pattern specified by a regular expression and "no" otherwise. A transition diagram or finite automaton depicts the actions that take place in the recognizer in the acquisition of tokens. A token is a sequence of characters having a collective meaning.
FIG. 2 shows a prior art method for searching text files in the above described manner and FIG. 3 shows an apparatus for implementing this method. Referring to FIG. 2, the prior art searching method is shown generally at 200. At step 1 at 210, regular expressions that define the patterns to be searched for are input to an appropriate apparatus designed and configured to conduct the search. At step 2 at 220, the regular expressions that are input to the apparatus are used to generate conventional finite automata. Step 3 at 230 is where the text file to be searched is input to the apparatus capable of conducting the search. This also is where the text file is searched for the desired patterns. Following this, at step 4 at 240, the results of the search are output from the searching apparatus.
Referring to the FIG. 3, a block diagram of the system for implementing the method of FIG. 2 is shown generally at 250. The regular expressions based on the patterns to be searched for are input to the apparatus at regular expression input 251 and then placed on line 252. The regular expressions constitute the first input to system 250.
The regular expressions on line 252 are input to generator 254 that generates conventional finite automata from these regular expressions. The conventional finite automata are output from generator 254 on line 256. The finite automata just generated are input to analyzer 260.
The second input to system 250 is the text file that is to be searched. It is input at text file input 257. The text file input connects to line 258, so the text file on line 258 is input to analyzer 260. Analyzer 260 uses the conventional finite automata to search the text file for patterns. The results of the search are output from analyzer 260 on line 262.
Lexical analyzers used in compilers often use an extension of this method to search text files. Lexical analyzers combine the finite automata from several regular expressions into a single finite automaton to partition the text file into a series of tokens. Each character of the text file is placed into exactly one token. No character is ever placed in two or more tokens. Therefore, no two tokens in the series overlap. The techniques of the prior art may be applied to trace arrays by considering tokens as events. Hence, a series of tokens may be viewed as a series of nonoverlapping events.
These methods of handling text files discussed above are discussed in Aho et al., "Chapter 3: Lexical Analysis," Compilers: Principles, Techniques, and Tools, Addison-Wesley, 1986, and other sections of this text.
Trace arrays, which include the continuum of trace array sizes from small and conventional to large, often contain one or more series of overlapping events. That is, many trace arrays contain a single series of overlapping events or several parallel series of overlapping events. For example, a computer bus that is being analyzed may have two sets of signals: data signals and arbitration signals. On such a bus, the situation may arise where during a data transfer on the data signals, the arbitration signals may be determining which bus device will own the bus after that data transfer completes. Hence, two separate but related events are occurring simultaneously. Known searching techniques do not have an ability to analyze such complex overlapping sequences of events as this.
Referring now generally to the treatment of text files in the past, text files have been treated as a string of symbols. These symbols are based on alphabets of finite size. For example, a text file that is input on line 258 of system shown in FIG. 3 may be an ASCII text file. Each ASCII character of the ASCII character set is treated as one symbol. The ASCII character set is a finite alphabet that contains 128 characters as will be shown.
A finite automaton as it has been used in the prior art consists of:
1. A set of states "s." PA1 2. A finite set of input symbols that constitutes the input symbol alphabet. PA1 3. A transition function that maps state-symbol pairs to sets of states. PA1 4. A state "s.sub.0 " which is the start state. PA1 5. A set of states "F" that are the accepting states.
In FIG. 4, an example of a finite automaton represented in a transition graph for the regular expression (a.vertline.b)*abb is shown generally at 275. In that Figure, the nodes are the states and the labeled edges are transitions.
The regular expression (a.vertline.b)*abb is the set of all strings of a's or b's ending in abb. In defining the finite automaton as represented in the transition graph of FIG. 4, the set of states are {0, 1, 2, 3}, the input symbol alphabet is {a,b}, the start state is s.sub.0, and the accepting state is s.sub.3. The transition function may be represented by the transition table at Table 1.
TABLE 1 ______________________________________ Input Alphabet Symbol State a b ______________________________________ 0 {0,1} {0} 1 -- {2} 2 -- {3} ______________________________________
A transition function as used in this capacity specifies for each transition function pair (s,a), where "s" is a state of the finite automaton and a is a particular symbol of the finite input alphabet, the next state of the finite automaton. Consider, for example, a finite automaton with the transition function f(s,a). If the finite automaton is in state "s.sub.1 " and reads input symbol a, and f(s.sub.1,a)=s.sub.2, then the finite automaton will go to state s.sub.2.
In the prior art, it has been important that the symbols for use with a finite automaton come from a finite alphabet. If they do not and come from an input alphabet of infinite size, the transition function also will be of an infinite size; and as such, a system such as that shown at 250 (FIG. 3) could not implement the transition function. As will now be shown, even though a large trace array may be presented in the same manner as text files, it does not mean that these large trace arrays may be analyzed in the same manner as conventional text files because of the inability of the prior art methods to be able to use infinite alphabets.
A representative ASCII file will now be discussed to demonstrate the inability of prior art text file searching methods to search or analyze larger trace arrays. In ASCII text files, each ASCII character is represented by a 7-bit code. For the purpose of this example, the ASCII text file contains 100 characters. The text file, therefore, may be represented by a binary array containing 100 rows and 7 columns. Each row may store a single character from the text file; and, thus, each row may represent a single symbol of the input alphabet. The first character of the text file goes in the first row of the array, the second character goes in the second row, and so on for the 100 characters. Hence, reading the array from the first to the last row is the same as scanning the text file from beginning to end.
Now, consider representing a large trace array as a text file. If a trace array contains 192 columns and 524,288 rows, in the text file context, each row will represent one character of a character set. Thus, the trace array may be presented as a text file containing 524,288 characters and each character has a 192-bit code.
In analyzing conventional text files, a first given is that the text file uses a finite alphabet. The ASCII character set that uses a 7-bit code per character will have 2.sup.7 or 128 characters in that set. Such a text file is shown in FIG. 5 at 280. This text file has representative rows 281, 282, 283, 284, 285, 286, and 287; and representative columns 288, 289, 290, 291, 292, 293, and 294. The transition function is relatively easy to implement for finite automata using this ASCII character set as an input symbol alphabet.
On the other hand, the character set for the large trace array discussed above has a 192-bit code for each character. As would be known, the character set using 192-bit codes would contain 2.sup.192 or 6,277,101,735,386,680,763,835,789,423,207,666,416,102,355,444,464,034,512, 896 characters, which for all practical purposes is an infinite character set. Given this character set size, it would be extremely difficult, if not impossible, to implement a transition function for a finite automaton using such a character set as an input symbol alphabet.
The present invention overcomes the problems that have been described and provides a system and method to automatically and efficiently analyze large trace arrays, and a system and method that overcome the overlapping token restriction problem in trace arrays of any size.